1. Field of the Invention
The present invention relates to a path-search technology. More specifically, the present invention relates to a method of, a program for, and a system for speeding up a path search.
2. Description of the Related Art
In recent years, as the number of optimum traffic route-search services in car navigation systems and websites has increased, there has been a growing demand for a speeded-up technique for finding a route by use of a computer. In terms of computer science, this comes down to an algorithm of determining the shortest path in a weighted graph.
Incidentally, as a classic technique for an algorithm of determining the shortest path in a weighted graph, there has been known a technique called Dijkstra method. In essence, when the shortest path from a vertex a to a vertex z is determined in a graph G with this method, the shortest path from the vertex a to a certain one of vertices is firstly determined; then the shortest paths from the vertex a to all the vertices excluding the certain vertex whose shortest path has been determined are sequentially determined; and the processing is terminated when the shortest paths to the all the vertices are determined. This algorithm is guaranteed to always have a solution, but becomes unrealistic in terms of calculation amount when the number of vertices in the graph G is increased.
To solve this, various techniques improved in terms of calculation amount have been proposed. As one of those techniques, there is a technique called A* search. This technique is configured to speed up a calculation for the shortest path by using previously calculated upper and lower limits of the shortest path length between 2 vertices, and is specifically a technique as described below.
In the following description, given vertices v and w, assume that d(v,w) denotes the shortest path length from the vertex v to the vertex w, and that w(v,w) denotes the length of an edge connecting the vertices v and w to each other.
Firstly, in order to find the shortest path from a starting point s to a terminal t, the following conditions are defined as initial settings for each of the vertices v:
π(v): lower limit of d(v,t);k(v): k(s) := π(s) where v = s, and k(v) := ∞ where v ≠ s;d(v): d(s) := 0 where v = s, and d(v) := ∞ where v ≠ s;prev(v) = NULL; andvertex set S = {s}.
On this premise, search processing is performed in the following manner:
while (S is not empty) {from S, remove vertex v giving smallest value of k(v)for (perform following operations on all ofedges(v,w) extending from v) {if (k(w) > k(v) + w(v,w) − π(v) + π(w)) {k(w) := k(v) + w(v,w) − π(v) + π(w);d(w) := d(v) + w(v,w);prev(w) := v;if (d(w) + π(w) <= min(upper limit ofd(s,t), d(t))){S ← S∪{w};}}}}
A value finally assigned to d(t) is the shortest path length.
Additionally, assuming that t′, t″ . . . , denote vertices assigned to prev(t), prev(t′), . . . , respectively, “t←t′←t″← . . . ←s” is the shortest path.
It has been known that, when the upper and lower limits of d(v,w) are correctly given for any two vertices v and w, the abovementioned A* search correctly finds the shortest path. Additionally, it has been known that the higher an accuracy of the upper limit given to the A* search is, the faster the terminal can be reached. By intuition, a lower limit of the shortest path length of a path from the starting point s to the terminal t by way of the vertex v is stored in k(v) in this algorithm, and the shortest path length from the starting point s to the vertex v is stored in d(v).
Here, a part (a method of calculating the upper and lower limits of d(v,w)), which is a black box in the abovementioned A* search algorithm, has conventionally been a problem.
In connection with this problem, first of all, there is a technique described in “Computing the Shortest Path: A* Search Meets Graph Theory” by A. V. Goldberg and C. Harrelson (in Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005).
In this technique, a small number of (ten and several) vertices on a graph are selected as “landmarks,” and the shortest path lengths from the landmarks to each of vertices are stored. Then, a lower limit of the shortest path length between any two vertices is computed by using the stored shortest path lengths. Thus, this technique achieves a speed-up of search with A* search.
Additionally, also known is “Goal Directed The shortest path Queries Using Precomputed Cluster Distances” by Jens Maue, Peter Sanders, Domagoj Matijevic (in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA-06), LNCS 4007, 316-327, Springer, 2006).
In this technique, a graph is divided into a large number of clusters, and the shortest path lengths between the respective clusters are defined and stored. Then, upper and lower limits of the shortest path length between any two vertices are then computed by using the stored shortest path lengths. Thus, this technique achieves a speed-up of search with A* search by combining pruning based on the upper limit of the shortest path length with the A* search.
In both of these techniques, accuracies of “upper and lower limits of the shortest path length between any two vertices” which are used in the A* search greatly contribute to the speed-up of the algorithm. The technique described in “Computing the Shortest Path: A* Search Meets Graph Theory” by A. V. Goldberg and C. Harrelson (in Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005) (hereinafter referred to as “Goldberg”) has a shortcoming that, while information on a plurality of landmarks is used when the lower limit is calculated, the number of the landmarks themselves is small. The technique described in “Goal Directed Shortest Path Queries Using Precomputed Cluster Distances” by Jens Maue, Peter Sanders, Domagoj Matijevic (in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA-06), LNCS 4007, 316-327, Springer, 2006) (hereinafter referred to as “Maue”) has a shortcoming that, while the number of the clusters themselves is large, the number of information on the clusters used when the lower limit is calculated is small.
Among other conventional techniques, there is a technique disclosed in Japanese Patent Application Laid-open Publication No. 2006-201174. However, one of the inventors thereof is also listed as one of the authors of the abovementioned Goldberg, and the contents of the disclosure are roughly the same as those of the above-mentioned Goldberg.